/*
二维差分：
    给定数组g[n][m]，k次操作，每次使区间内各元素同时加一个数，如(1,2,2,3,5) <=> g[1][2]+=5,g[1][3]+=5,g[2][2]+=5,g[2][3]+=5。1次询问，问最后的arr数组。
*/

#include <bits/stdc++.h>
using namespace std;
const int n = 3, m = 4;
int d[n + 1][m + 1];
int g[n][m] = {
    {1, 5, 6, 8},
    {9, 6, 7, 3},
    {5, 3, 2, 4}};
int sum[n][m];
void add(int x1, int y1, int x2, int y2, int val)
{
    d[x1][y1] += val;
    d[x1][y2 + 1] -= val;
    d[x2 + 1][y1] -= val;
    d[x2 + 1][y2 + 1] += val;
}
void pre_sum()
{
    sum[0][0] = d[0][0];
    for (int i = 1; i < n; i++)
        sum[i][0] = sum[i - 1][0] + d[i][0];
    for (int j = 1; j < m; j++)
        sum[0][j] = sum[0][j - 1] + d[0][j];
    for (int i = 1; i < n; i++)
        for (int j = 1; j < m; j++)
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + d[i][j];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            g[i][j] += sum[i][j];
}
void print()
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            cout << g[i][j] << " ";
        cout << endl;
    }
}
int main()
{
    memset(sum, 0, sizeof(sum));
    memset(d, 0, sizeof(d));
    add(0, 0, 2, 1, 3);
    add(1, 1, 2, 2, -1);
    pre_sum();
    print();
    return 0;
}
